package cumt.oj;

/**
 * @Author Fizz Pu
 * @Date 2020/10/30 下午2:11
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */


import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 题目描述
 * 一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。
 * 没有一辆车子行驶超过10公里，一个顾客打算行驶n公里(1<=n<100)，
 * 它可以通过无限次的换车来完成旅程。最后要求费用最少。
 *
 *
 * 输入
 * 第一行十个整数分别表示行走1到10公里的费用(<=500)。注意这些数并无实际的经济意义，
 * 即行驶10公里费用可能比行驶一公里少。第二行一个整数n表示，旅客的总路程数。
 *
 * 输出
 * 仅一个整数表示最少费用。
 *
 *
 * 样例输入
 * 12 21 31 40 49 58 69 79 90 101
 * 15
 * 一公里： 12
 * 二公里： 21
 * 三公里： 12 + 21, 21 + 12, 31
 * 四公里： 第一辆车 12 ， 21 ， 31 ，41 ， 剩下公里的最优值查表
 * 11公里： 第一辆车可以做1,2,3,4,5,6,7,8,9，10
 * n公里： math.min(a[i] + a(n-i)) i为0到10
 * 样例输出
 * 147
 */


public class CarCost {

    public int getMinCost(int[] cost, int distance){


        // dp[i]表示行驶i公里的最优花费
        int[] dp = new int[distance+1];

        // 初始值
        dp[0] = 0;
        dp[1] = cost[0];
        dp[2] = Math.min(cost[1], cost[0] + cost[0]);

        // 循环填表
        for(int dis = 3; dis <= distance; ++dis){
            int min = Integer.MAX_VALUE;
            int s = Math.min(dis, cost.length);
            for(int first = 1; first <= s; ++first){ // 第一辆车走的公里数1到10之间
                min = Math.min(cost[first-1] + dp[dis-first], min);
            }
            dp[dis] = min;
        }

        // 返回结果
        return dp[distance];
    }

}


/*
public class Main{
    public static void main(String[] args) {
        CarCost carCost = new CarCost();
        Scanner scanner = new Scanner(System.in);
        int [] cost = new int[10];
        int distance;

        for(int i = 0; i < 10; ++i){
            cost[i] = scanner.nextInt();
        }
        distance = scanner.nextInt();

        System.out.println(carCost.getMinCost(cost, distance));
    }
}*/
